<?php
/*
 * 给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
*/

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) {
        $this->val = $value;
    }
}

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val)
    {
        $this->val = $val;
    }
}

class Solution {

    /**
     * @param ListNode $head
     * @param TreeNode $root
     * @return Boolean
     */
    function isSubPath($head, $root) {
        if ($root == null) {
            return false;
        }
        if ($head == null) {
            return true;
        }
        // 先判断当前的节点，如果不对，再看左子树和右子树
        return $this->isSub($head, $root) || $this->isSubPath($head, $root->left) || $this->isSubPath($head, $root->right);
    }

    function isSub($list_node, $tree_node)
    {
        // 特判：链表走完了，返回true
        if ($list_node == null) {
            return true;
        }
        // 特判：链表没走完，树走完了，这肯定不行，返回false
        if ($tree_node == null) {
            return false;
        }
        // 如果值不同，必定不是
        if ($list_node->val != $tree_node->val) {
            return false;
        }
        // 如果值相同，继续看，左边和右边有一个满足即可
        return $this->isSub($list_node->next, $tree_node->left) || $this->isSub($list_node->next, $tree_node->right);
    }
}
